public class DynamicProgram {

//    打家劫舍 滚动数组
/*
                房子   0  1  2  3     H[i]  表示i间房藏有的金额数
                金额   1  2  3  1     S[i]  表示偷窃钱S[i]之前可以获得最大金额数
    设dp为最大偷钱数
    第一间房子  S[0] = H[0] =1
    第二间房子  可以不偷或者偷 看哪个房子更有钱  这里偷  S[1] = max(S[0],H[1]) = 2   max内前者表示不偷这家 后者表示偷
    第三间房子  S[2] = max(S[1],H[2]+S[0])
    第四间房子  S[3] = max(S[2],H[3]+S[2])
    使用有递推公式  S[n] = max(S[n-1],H[n]+S[n-1]
    https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/?orderBy=most_relevant&languageTags=java
*/
    public int rob(int[] nums) {
//        int length = nums.length;//写在前面 当nums为null时 报错NullPointerException
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (nums.length == 1) {
            return nums[0];
        }

//        到这length的长度 大于等于2
//        dp表示偷窃钱前可以获得最大金额数
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i-1], nums[i]+dp[i-2]);  //max内 前者表示不偷 后者表示偷
        }
        return dp[length-1];
    }

}
